package list.ReverseList;

import list.ListNode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @ClassName ReverseListK
 * @Description TODO
 * @Author lenovo
 * @Date 2023-02-15 9:44
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class ReverseListK {

    /**
     * 题目
     * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
     * <p>
     * k 是一个正整数，它的值小于或等于链表的长度。
     * <p>
     * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
     * <p>
     * 示例1：
     * <p>
     * 输入：head = [1,2,3,4,5], k = 2
     * 输出：[2,1,4,3,5]
     * 1
     * 2
     * 示例2：
     * <p>
     * 输入：head = [1,2,3,4,5], k = 3
     * 输出：[3,2,1,4,5]
     * 1
     * 2
     * 示例3：
     * <p>
     * 输入：head = [1,2,3,4,5], k = 1
     * 输出：[1,2,3,4,5]
     * 1
     * 2
     * 示例4：
     * <p>
     * 输入：head = [1], k = 1
     * 输出：[1]
     * 1
     * 2
     * 思路
     * 这个问题主要有两个点，1个是k个结点，2是进行翻转
     * <p>
     * k个结点可以使用快慢结点来解决
     */

    public ListNode reverseKGroup(ListNode head, int k) {
        Deque<ListNode> stack = new LinkedList<>();

        ListNode yummy = new ListNode(0);
        yummy.next = head;
        ListNode cur = yummy;

        while (true) {
            int count = 0;
            ListNode temp = head;

            while (temp != null && count < k) {
                stack.push(temp);
                temp = temp.next;
                count++;
            }

            if (count != k) {
                cur.next = head;
                break;
            }

            while (!stack.isEmpty()) {
                ListNode popListNode = stack.pop();
                cur.next = popListNode;
                cur = cur.next;
            }
            head = temp;
        }
        return yummy.next;
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        ListNode head2 = new ListNode(2);
        ListNode head3 = new ListNode(3);
        ListNode head4 = new ListNode(4);
        head1.next = head2;
        head2.next = head3;
        head3.next = head4;
        ReverseListK reverseListK = new ReverseListK();
        System.out.println(reverseListK.reverseKGroup(head1, 2));
    }
}